<?php
/**
 * @title 1025. 除数博弈
 * @author start2004
 */


class Solution {
    public $dps = [];

    /**
     * @param Integer $N
     * @return Boolean
     */
    function divisorGame($N) {
        if(isset($this->dps[$N])){
            return $this->dps[$N];
        } else {}

        /**
         * @since 2020-10-13 取模为0, 最大值一半
         */
        $half = $N>>1;

        /**
         * @since 2020-10-13 取模为0的数
         */
        for ($x=1; $x<=$half; $x++){
            if($N % $x == 0){
                if(self::divisorGame($N-$x) === false){
                    $this->dps[$N] = true;
                    return true;
                    break;
                } else {}
            } else {}
        }

        /**
         * @return
         */
        $this->dps[$N] = false;
        return false;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.24_4.php
 */
$datas = [
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10,
    11,
    12,
    13,
    14,
    15,
    16,
    17,
    18,
    19,
    20,
    1000,
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->divisorGame($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
